from tools_algorithm import *


class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        q = []
        for i, num in enumerate(nums):
            heappush(q, (num, i))
        for _ in range(k):
            heapreplace(q, (q[0][0] * multiplier, q[0][1]))
        ans = [0] * len(nums)
        while q:
            c = heappop(q)
            ans[c[1]] = c[0]
        return ans
